package Union;

public class Test {
    /*查找一个图中有多少个相邻的岛
    *  深度优先*/
    public static int countIslands(int[][] m){
        //时间复杂度O(M * M)
        if (m == null || m[0] == null){
            return 0;
        }
        int N = m.length;
        int M = m[0].length;
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (m[i][j] == 1){
                    res++;
                    infect(m,i,j,N,M);
                }
            }
        }
        return res;
    }
    public static void infect(int[][] m,int i,int j,int N,int M){
        if (i < 0 || i >= N || j < 0 || j >= M || m[i][j] == 1){
            return;
        }
        // i ,j 没有越界,并且当前的位置是一个有效位置.
        m[i][j] = 2;//不会死循环的关键
        infect(m,i+1,j,N,M);
        infect(m,i-1,j,N,M);
        infect(m,i,j+1,N,M);
        infect(m,i,j-1,N,M);

    }
    //并查集解决

}
